package leetcode;
/**
 * KY11 二叉树的遍历
 * 编写一个程序读入用户输入的一串先序遍历字符串，根据此字符串创建一个二叉树，再对二叉树进行中序遍历，输出遍历结果。(要求多行输入)
 *
 * 样例输入：abc##de#g##f### （#表示空树）
 * 样例输出：c b e g d f a
 */
import java.util.*;
public class NowCoder_KY11 {

    //字符串遍历时的每一个字符位置
    private static int index = 0;

    //二叉树节点类
    private static class TreeNode {
        char val;
        TreeNode left;
        TreeNode right;
        TreeNode() {
        }
        TreeNode(char val) {
            this.val = val;
        }
        TreeNode(char val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

    public static void main(String[] args) {
        Scanner input = new Scanner(System.in);
        //多行输入
        while(input.hasNext()){
            String str = input.nextLine();
            index = 0;
            TreeNode root = buildTreeNode(str);
            System.out.println(inorderTraversal(root));
        }
    }

    //根据字符串(二叉树的前序遍历结果集)创建一颗二叉树，并返回根节点
    private static TreeNode buildTreeNode(String str) {
        if(str.charAt(index) == '#'){
            return null;
        }
        //创建根节点
        TreeNode root = new TreeNode(str.charAt(index));
        index ++;
        //递归创建左子树
        root.left = buildTreeNode(str);
        index ++;
        //递归处理右子树
        root.right = buildTreeNode(str);
        //返回二叉树的根节点
        return root;
    }

    //将二叉树的中序遍历结果返回为字符串
    private static StringBuilder sb = new StringBuilder();
    private static String inorderTraversal(TreeNode root) {
        if(root == null){
            return "";
        }
        inorderTraversal(root.left);
        sb.append(root.val);
        sb.append(" ");
        inorderTraversal(root.right);
        return sb.toString();
    }
}
